package com.sakura.双指针;

/**
 * <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array/">链接</a>
 */
public class Code26_删除有序数组中的重复项 {

    /**
     注意：数组有序的，说明重复元素是相邻的，那么我们找到第一个与前面不相同的值，就交换指针位置的值，并让前指针移动一位
     首先定义两个指针，i，j。 i 记录前一个，j 记录后一个
     从j位置开始遍历，判断i j 位置值是否相等。此时有两种情况
     1. i 位置与 j 位置的值相等，那么就无需做变化 j 指针继续移动就好
     2. i 位置与 j 位置的值相等，那么就将 i + 1 位置的值和j位置的值，交换，然后移动i 再移动j

     最后，i所在位置就是数组中无重复元素最后一个元素的下标，因此返回值要+1
     */
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int n = nums.length;
        int j = i + 1;
        while (j < n) {
            if (nums[i] != nums[j]) {
                if (j - i > 1) { // 优化，避免重复复制值
                    nums[i + 1] = nums[j];
                }
                i++;
            }
            j++;
        }
        return i + 1;
    }
}
